package Year22_Month07.day02;


import java.util.LinkedList;
import java.util.List;

public class 有效IP地址 {
    List<String> resList = new LinkedList<>();
    StringBuilder stringBuilder = new StringBuilder();
    public List<String> restoreIpAddresses(String s) {
        if(s.length() > 12){
            return resList;
        }
        backstracking(s,0,0);
        return resList;
    }
    //count用来记录当前的小数点的个数
    public void backstracking(String str,int startIndex,int count){
        if(str.length() == startIndex && count == 4){
            resList.add(stringBuilder.toString());
            return;
        }
        //如果说开始起始下标和结束下标一致，但是小数点数量不够，那么就直接return就行
        if(str.length() == startIndex || count == 4){
            return;
        }

        for (int i = startIndex; i < str.length() && i - startIndex < 3 &&
                     Integer.parseInt(str.substring(startIndex,i)) >= 0 &&
                Integer.parseInt(str.substring(startIndex,i)) <= 255; i++) {
            if(i + 1 - startIndex > 0 && str.charAt(startIndex) - '0' == 0){
                continue;
            }
            stringBuilder.append(str.substring(startIndex,i + 1));
            if(count < 3){
                stringBuilder.append('.');
            }
            count++;
            backstracking(str,i + 2,count);
            count--;
            stringBuilder.delete(startIndex + count,i + count + 2);
        }
    }
}
